Secret sharing (or threshold secret sharing) is a cryptographic scheme that divides a secret into n pieces (or shares) such that any k of them (k<n) can be used to reconstruct the secret.
Conventional techniques for secret sharing generally use integer mathematics in the calculation of the shares and the reconstruction of the secret from the shares. Adi Shamir discloses a technique that uses polynomial interpolations in the finite field GF(p), where p is a prime number, to construct a threshold secret sharing scheme (A. Shamir, “How to Share a Secret,” Communications of the ACM, v. 24, n. 11, November 1979, pp. 612-613). For example, to create a (3, n) threshold scheme (that is, three shares out of n shares are necessary to reconstruct a secret), a quadratic polynomial is generated as (ax2+bx+M) modulo p, where a and b are random numbers, and M is the secret. Each of a, b and M is an integer number. The n shares are obtained by evaluating the polynomial at n distinct non-zero points (each of the n points being an integer number), and the shares are distributed to n cooperating parties. Each of the n shares includes a pair of numbers (x, y), where x is one of the distinct points and y is a corresponding result. To reconstruct the secret, a Lagrange polynomial can be constructed to interpolate the points (x, y) defined by any three shares, and the secret M can be obtained by computing the constant term of the Lagrange polynomial.
Conventional techniques, such as the one described above, perform operations over a field of a prime number, which potentially requires the use of very large integer mathematics. Large integer mathematics can be complex and time-consuming. Thus, there is a need to develop a secret sharing technique that overcomes the above inherent limitations of the known techniques.